package org.zxp.algorithm.sort;

import org.zxp.algorithm.sort.utils.Tools;

import java.util.Arrays;
import java.util.Random;

/**
 * @program: effectiveJava
 * @description:归并排序
 * @author: X-Pacific zhang
 * @create: 2019-07-25 15:20
 **/
public class MergeSort {
    public static void main(String[] args) throws Exception {
        int[] sorts = {4,5,3,2,7,9,2,5};
        long time1 = System.currentTimeMillis();
        sorts = Tools.gen(10000000);
        long time2 = System.currentTimeMillis();
        MergeSort.m_sort(sorts,0,sorts.length-1);
        long time3 = System.currentTimeMillis();
        Tools.printResult(sorts, time1, time2, time3,"归并");
//        Tools.print(sorts);
    }


    //arr[m-n] = merge(m_sort(m-r),m_sort(r+1 - n))
    //m>n

    public static void m_sort(int[] a,int begin,int end){
        if(begin >= end){
            return;
        }
       int middle = (end - begin)/2 + begin;//找中点
        m_sort(a, begin, middle);//前半段进行归并排序，在原数组上
        m_sort(a, middle+1, end);//后半段进行归并排序，在原数组上
        merge(a,begin,middle,end);//排序后将前后半段按照算法进行合并（这里是发生真正排序的地方）
    }

    public static void merge(int[] a,int begin,int middle,int end){
        int[] tmp = new int[end-begin+1];//构建本次临时数组，最后再将临时数组的值复制给原数组，这里是需要额外的空间的地方
        int i = begin;//前段开始下标，前段此时已经有序
        int j = middle + 1;//后段开始下标，后段此时已经有序
        int k = 0;//临时数组游标

        while(true){
            if(i > middle){//当遍历前段的下标大于中点时，说明前段已经遍历完成
                for(;j <= end;j++){//把后段的数据全部复制到临时数组中
                    tmp[k++] = a[j];
                }
                break;
            }
            if(j > end){//当遍历后段的下标大于终点时，说明后段已经遍历完成
                for(;i <= middle;i++){//把前段的数据全部复制到临时数组中
                    tmp[k++] = a[i];
                }
                break;
            }
            if(a[i] <= a[j]){//如果前半段游标与后半段游标对应值相比
                tmp[k++] = a[i++];//小的拷贝到数组中，并游标++
            }else{
                tmp[k++] = a[j++];
            }
        }
        //在将本次重新合并的结果重新放入数组中
        for (i = 0; i <= end-begin; i++) {
            a[begin+i] = tmp[i];
        }
    }


}
